// https://leetcode.cn/problems/increasing-triplet-subsequence/
// Created by ade on 2022/11/1.
//
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 单调栈解法
    bool increasingTriplet1(vector<int> &nums) {
        vector<int> st;
        vector <vector<int>> res;
        vector<int> newNums = {nums[0]};
        for (int i = 1; i < nums.size(); i++) {
            if (newNums.back() != nums[i]) newNums.push_back(nums[i]);
        }

        for (auto &i:newNums) {
            if (st.empty() || i > st.back()) {
                st.push_back(i);
                continue;
            }
            if (st.size() >= 3) return true;
            if (st.size() == 2)
                res.push_back(st);
            while (!st.empty() && i <= st.back()) {
                st.pop_back();
            }
            st.push_back(i);
            if (st.size() >= 3) return true;
        }
        if (st.size() >= 3) return true;
        if (st.size() == 2)
            res.push_back(st);
        for (int i = 1; i < res.size(); i++) {
            if (res[i - 1].size() == 2 && res[i].size() == 2 && res[i][1] > res[i - 1][1]) return true;
        }
        return false;
    }

    // 双向遍历
    bool increasingTriplet(vector<int> &nums) {
        // 这种方法复杂度O(N^2)会超时
        /*vector<int> newNums = {nums[0]};
        for (int i = 1; i < nums.size(); i++) {
            if (newNums.back() != nums[i]) newNums.push_back(nums[i]);
        }
        int len = newNums.size();
        for (int i = 1; i < len - 1; i++) {
            int lf = 0, rf = 0;
            for (int l = 0; l < i; l++) {
                if (newNums[l] < newNums[i]) {
                    lf = 1;
                    break;
                }
            }
            if (lf == 0) continue;
            for (int r = i + 1; r < len; r++) {
                if (newNums[r] > newNums[i]) {
                    rf = 1;
                    break;
                }
            }
            if (rf) return true;
        }
        return false;*/
        // 这种方法O(3*N)
        /*int n = nums.size();
        vector<int> minArr(n);
        minArr[0] = nums[0];
        vector<int> maxArr(n);
        maxArr[n - 1] = nums[n - 1];
        for (int i = 1; i < n; i++) {
            minArr[i] = min(minArr[i - 1], nums[i - 1]);
            maxArr[n - 1 - i] = max(maxArr[n - i], nums[n - i]);
        }
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > minArr[i] && nums[i] < maxArr[i]) return true;
        }
        return false;*/

        // 贪心是O(N)复杂度的
        int n = nums.size();
        int first = nums[0], second = INT_MAX;
        for (int i = 1; i < n; i++) {
            if(nums[i] > second) return true;
            else if(nums[i] > first) second = nums[i];
            else if(nums[i] < first) first = nums[i];
        }
        return false;
    }
};

int main() {
    Solution so;
    vector<int> nums = {2, 4, -2, 3};
    cout << so.increasingTriplet(nums);
    return 0;
}